package com.javabasic.algorithm.leetcode;

/**
 * @author mir.xiong
 * @version 1.0
 * @description
 * @see [498. 对角线遍历 - 力扣（LeetCode）](https://leetcode.cn/problems/diagonal-traverse/)
 * @since Created by work on 2022/6/14 23:06
 */
public class DiagonalTraverse {

    /**
     * 类似蛇形填数，思维逻辑 + 发现规律
     * @param mat
     * @return
     */
    public int[] findDiagonalOrder(int[][] mat) {

        int lenX = mat.length;
        int lenY = mat[0].length;
        int tag = 1;
        int[] result = new int[lenX * lenY];
        int index = 0;
        int x = 0, y = 0;

        while (true) {
            result[index++] = mat[x][y];
            if ((tag & 1) == 1) {
                x -= 1;
                y += 1;
            } else {
                x += 1;
                y -= 1;
            }
            if (isOutOfBound(x, y, lenX, lenY)) {
                if (isEnd(x, y, lenX, lenY)) {
                    break;
                }
                int direct = getDirect(x, y, lenX, lenY);
                switch (direct) {
                    case 1:
                        x += 1;
                        break;
                    case 2:
                        x += 2;
                        y -= 1;
                        break;
                    case 3:
                        x -= 1;
                        y += 2;
                        break;
                    case 4:
                        y += 1;
                }

                tag++;
            }
        }

        return result;
    }

    /**
     * 越界方向
     * @param x
     * @param y
     * @param lenX
     * @param lenY
     * @return
     */
    private int getDirect(int x, int y, int lenX, int lenY) {
        // 上越界
        if (x == -1 && (y >= 0 && y < lenY)) return 1;
        // 右越界
        if (y == lenY && (x >= -1 && x < lenX)) return 2;
        // 下越界
        if (x == lenX && (y >= -1 && y < lenY)) return 3;
        // 左越界
        if (y == -1 && (x >= 0 && x < lenX)) return 4;
        return 0;
    }

    /**
     * 是否越界
     * @param x
     * @param y
     * @param lenX
     * @param lenY
     * @return
     */
    private boolean isOutOfBound(int x, int y, int lenX, int lenY) {
        return x >= lenX || x < 0 || y >= lenY || y < 0;
    }

    /**
     * 是否为终点下标
     * @param x
     * @param y
     * @param lenX
     * @param lenY
     * @return
     */
    public boolean isEnd(int x, int y, int lenX, int lenY) {
        return (x == lenX && y == lenY - 2) || (x == lenX - 2 && y == lenY);
    }
}
